//
//$Id: re.cpp 687 2011-03-13 12:21:29Z Andrew.Tsyganov $
#include "stdafx.h"

#include "include/re.h"
#include "include/fa.h"

using namespace std;

void REToFA(RE const& re, FA& fa)
{
	u_t m = re.get_Symbols_Num();
	vector<u_t> const& postfix = re.get_Postfix();

	if (postfix.empty())
	{
		fa.init(re.get_Name(), m, 0, re.get_Epsilon());
		fa.set_Symbols(re.get_Symbols());
		return;
	}

	stack<FA> operands;

	for (u_t i = 0; i < postfix.size(); ++i)
	{
		u_t code = postfix[i];
		
		if (re.operand(code))
		{
			FA a("", m, 2, "");

			a.set_Initial(0);
			a.set_Final(1);

			if (re.lexeme(code) != "@")
			{
				a.add_Transition(0, code, 1);
			}

			operands.push(a);
		}
		else
		{
			if (re.lexeme(code) == "+")
			{
				FA fa1, fa2, fa3;
				fa2 = operands.top();
				operands.pop();
				fa1 = operands.top();
				operands.pop();
				Join(fa1, fa2, fa3);
				operands.push(fa3);
			}

			if (re.lexeme(code) == ".")
			{
				FA fa1, fa2, fa3;
				fa2 = operands.top();
				operands.pop();
				fa1 = operands.top();
				operands.pop();
				Concat(fa1, fa2, fa3);
				operands.push(fa3);
			}

			if (re.lexeme(code) == "*")
			{
				FA fa1, fa2;
				fa1 = operands.top();
				operands.pop();
				Star(fa1, fa2);
				operands.push(fa2);
			}
		}
	}

	fa = operands.top();
	fa.set_Name("aut(" + re.get_Name() + ")");
	fa.set_Symbols(re.get_Symbols());
	fa.set_Epsilon(re.get_Epsilon());
	operands.pop();
}

bool Concat(FA const& fa1, FA const& fa2, FA& fa3)
{
	u_t m = fa1.get_Symbols_Num();

	if (m != fa2.get_Symbols_Num())
	{
		cout << "Concat error: automata should have the same number of symbols!" << endl;
		return false;
	}

	if (fa1.get_Symbols() != fa2.get_Symbols())
	{
		cout << "Concat error: automata should have the same symbols_ vectors!" << endl;
		return false;
	}

	if (!fa1.get_States().empty() || !fa2.get_States().empty())
	{
		cout << "Concat error: automata states_ vector should be empty!" << endl;
		return false;
	}

	if ((fa1.get_Initial().size() != 1) || (fa1.get_Final().size() != 1) || (fa2.get_Initial().size() != 1) || (fa2.get_Final().size() != 1))
	{
		cout << "Concat error: automata should have 1 initial and 1 final states!" << endl;
		return false;
	}

	u_t n1 = fa1.get_States_Num();
	u_t n2 = fa2.get_States_Num();

	fa3 = fa1;
	fa3.set_Name("");
	fa3.add_States(n2);

	vector<Adjacent> const& delta2 = fa2.get_Delta();

	// copy transitions of fa2
	for (u_t i = 0; i < n2; ++i)
	{
		for (Adjacent::const_iterator it_a = delta2[i].begin(); it_a != delta2[i].end(); ++it_a)
		{
			Subset dst = it_a->second;
			Subset new_dst;
			
			for (Subset::iterator it_d = dst.begin(); it_d != dst.end(); ++it_d)
			{
				new_dst.insert(n1 + *it_d);
			}

			fa3.add_Transitions(n1 + i, it_a->first, new_dst);
		}
	}

	u_t fin1_id = fa1.get_Final().get_By_Count(0);
	u_t in2_id = fa2.get_Initial().get_By_Count(0);
	u_t fin2_id = fa2.get_Final().get_By_Count(0);

	// change final state
	fa3.reset_Final();
	fa3.set_Final(n1 + fin2_id);


	// add epsilon transition
	fa3.add_Transition(fin1_id, m, n1 + in2_id);

	return true;
}

bool Join(FA const& fa1, FA const& fa2, FA& fa3)
{
	u_t m = fa1.get_Symbols_Num();

	if (m != fa2.get_Symbols_Num())
	{
		cout << "Join error: automata should have the same number of symbols!" << endl;
		return false;
	}

	if (fa1.get_Symbols() != fa2.get_Symbols())
	{
		cout << "Join error: automata should have the same symbols_ vectors!" << endl;
		return false;
	}

	if (!fa1.get_States().empty() || !fa2.get_States().empty())
	{
		cout << "Join error: automata states_ vector should be empty!" << endl;
		return false;
	}

	if ((fa1.get_Initial().size() != 1) || (fa1.get_Final().size() != 1) || (fa2.get_Initial().size() != 1) || (fa2.get_Final().size() != 1))
	{
		cout << "Join error: automata should have 1 initial and 1 final states!" << endl;
		return false;
	}

	u_t n1 = fa1.get_States_Num();
	u_t n2 = fa2.get_States_Num();

	fa3.init("", m, 2 + n1 + n2, fa1.get_Epsilon());

	vector<Adjacent> const& delta1 = fa1.get_Delta();
	vector<Adjacent> const& delta2 = fa2.get_Delta();

	// copy transitions of fa1
	for (u_t i = 0; i < n1; ++i)
	{
		for (Adjacent::const_iterator it_a = delta1[i].begin(); it_a != delta1[i].end(); ++it_a)
		{
			Subset dst = it_a->second;
			Subset new_dst;
			
			for (Subset::iterator it_d = dst.begin(); it_d != dst.end(); ++it_d)
			{
				new_dst.insert(1 + *it_d);
			}

			fa3.add_Transitions(1 + i, it_a->first, new_dst);
		}
	}

	// copy transitions of fa1
	for (u_t i = 0; i < n2; ++i)
	{
		for (Adjacent::const_iterator it_a = delta2[i].begin(); it_a != delta2[i].end(); ++it_a)
		{
			Subset dst = it_a->second;
			Subset new_dst;
			
			for (Subset::iterator it_d = dst.begin(); it_d != dst.end(); ++it_d)
			{
				new_dst.insert(1 + n1 + *it_d);
			}

			fa3.add_Transitions(1 + n1 + i, it_a->first, new_dst);
		}
	}

	u_t in1_id = fa1.get_Initial().get_By_Count(0);
	u_t fin1_id = fa1.get_Final().get_By_Count(0);
	u_t in2_id = fa2.get_Initial().get_By_Count(0);
	u_t fin2_id = fa2.get_Final().get_By_Count(0);

	// set initial and final states
	fa3.set_Initial(0);
	fa3.set_Final(1 + n1 + n2);

	// add epsilon transition
	fa3.add_Transition(0, m, 1 + in1_id);
	fa3.add_Transition(0, m, 1 + n1 + in2_id);
	fa3.add_Transition(1 + fin1_id, m, 1 + n1 + n2);
	fa3.add_Transition(1 + n1 + fin2_id, m, 1 + n1 + n2);

	return true;
}

bool Star(FA const& fa1, FA& fa2)
{
	if (!fa1.get_States().empty())
	{
		cout << "Star error: automaton states_ vector should be empty!" << endl;
		return false;
	}

	if ((fa1.get_Initial().size() != 1) || (fa1.get_Final().size() != 1))
	{
		cout << "Star error: automaton should have 1 initial and 1 final states!" << endl;
		return false;
	}

	u_t n = fa1.get_States_Num();
	u_t m = fa1.get_Symbols_Num();
	u_t in_id = fa1.get_Initial().get_By_Count(0);
	u_t fin_id = fa1.get_Final().get_By_Count(0);

	fa2 = fa1;
	fa2.set_Name("");
	
	fa2.add_State();

	// change final state
	fa2.reset_Final();
	fa2.set_Final(n);

	// add epsilon transitions
	fa2.add_Transition(fin_id, m, in_id); 
	fa2.add_Transition(fin_id, m, n); 
	fa2.add_Transition(in_id, m, n); 

	return true;
}

//EOF!

